//
//  Problem1370.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1370. 上升下降字符串 【字符计算】
 给你一个字符串 s ，请你根据下面的算法重新构造字符串：

 1:从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
 2:从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
 3:重复步骤 2 ，直到你没法从 s 中选择字符。
 4:从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
 5:从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
 6:重复步骤 5 ，直到你没法从 s 中选择字符。
 7:重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
 请你返回将 s 中字符重新排序后的 结果字符串 。

 示例 1：
     输入：s = "aaaabbbbcccc"
     输出："abccbaabccba"
     解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
     第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
     第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
     第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
     第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"
 示例 2：
     输入：s = "rat"
     输出："art"
     解释：单词 "rat" 在上述算法重排序以后变成 "art"
 示例 3：
     输入：s = "leetcode"
     输出："cdelotee"
 示例 4：
     输入：s = "ggggggg"
     输出："ggggggg"
 示例 5：
     输入：s = "spo"
     输出："ops"
 提示：
     1 <= s.length <= 500
     s 只包含小写英文字母。
 */
@objcMembers class Problem1370: NSObject {
    func solution() {
        print(sortStringAssi("aaaabbbbcccc"))
        print(sortStringAssi("leetcode"))
        print(sortStringAssi("rat"))
        print(sortStringAssi("ggggggg"))
        print(sortStringAssi("spo"))
    }
    
    var ascii:[Character : Int] = [
            "a" : 97,
            "b" : 98,
            "c" : 99,
            "d" : 100,
            "e" : 101,
            "f" : 102,
            "g" : 103,
            "h" : 104,
            "i" : 105,
            "j" : 106,
            "k" : 107,
            "l" : 108,
            "m" : 109,
            "n" : 110,
            "o" : 111,
            "p" : 112,
            "q" : 113,
            "r" : 114,
            "s" : 115,
            "t" : 116,
            "u" : 117,
            "v" : 118,
            "w" : 119,
            "x" : 120,
            "y" : 121,
            "z" : 122
        ]
    
    /*
     1: 创建一个字典, 存储a~z的个数
     2: 反序遍历。正序遍历。反序遍历。正序遍历。
     */
    func sortString(_ s: String) -> String {
        var dp:[Character: Int] = [:]
        for c in s {
            if dp[c] == nil {
                dp[c] = 1
            } else {
                dp[c]! += 1
            }
            
        }
        
        // 特例：只有一个字符
        if dp.count == 1 {
            return s
        }
        
        var arrays = dp.sorted { (arg0, arg1) -> Bool in
            let (key1, _) = arg1
            let (key2, _) = arg0
            return key1 > key2
        }
        
        var results:[Character] = []

        var isLast = true
        while arrays.count > 0 {
            if isLast == true {
                for i in 0..<arrays.count {
                    results.append(arrays[i].key)
                    arrays[i].value -= 1
                }
            } else {
                for i in (0..<arrays.count).reversed() {
                    results.append(arrays[i].key)
                    arrays[i].value -= 1
                }
            }
            isLast = !isLast
            
            arrays.removeAll { (key, value) -> Bool in
                return value <= 0
            }
        }
        
        return String(results)
    }
    
    func sortStringAssi(_ s: String) -> String {
        var charts = Array(repeating: 0, count: 26)
        for c in s {
            charts[Int(c.asciiValue!) - 97] += 1
        }
        
        var results:[Character] = []
        
        while results.count < s.count {
            // 正序
            for i in 0..<26 {
                if charts[i] != 0 {
                    let char = Character(Unicode.Scalar(i + 97)!)
                    results.append(char)
                    charts[i] -= 1
                }
            }
            
            // 倒序
            for i in (0..<26).reversed() {
                if charts[i] != 0 {
                    let char = Character(Unicode.Scalar(i + 97)!)
                    results.append(char)
                    charts[i] -= 1
                }
            }
        }
        
        return String(results)
    }
}
